# To change this template, choose Tools | Templates
# and open the template in the editor.

__author__="jonathan"
__date__ ="$22-Jun-2010 20:46:26$"

class Grid(object):

    def __init__(self, objs, central_pos):
        grid = {}
        for (x, y), obj in objs.iteritems():
            link = GridLink(obj)
            grid[(x, y)] = link

        for (x, y), link in grid.iteritems():
            # Connect the link on the left to this one.
            if (x-1, y) in grid:
                grid[(x-1, y)].right = link
            # Connect the link on the right to this one.
            if (x+1, y) in grid:
                grid[(x+1, y)].left = link
            # Connect the link below to this one.
            if (x, y+1) in grid:
                grid[(x, y+1)].up = link
            # Connect the link above to this one.
            if (x, y-1) in grid:
                grid[(x, y-1)].down = link

        assert central_pos in grid, "central_pos must be in the grid."
        self.center = grid[central_pos]

    def apply(self, func, filter=None, set_center=None):
        """Apply a function to each link in the grid starting at the middle
        and expanding outwards subject to the filter.
        """
        assert callable(func), "func myust be a callable."
        if filter is not None:
            assert callable(filter), "filter must be callable."
        if set_center is not None:
            assert callable(set_center), "set_center must be callable."

        self.new_center = None
        self.applied_to = set()
        self._apply(func, filter, set_center, self.center)

        # If we have a new center now is the time to update.
        if self.new_center is not None:
            self.center = self.new_center

    def _apply(self, func, filter, set_center, grid_link):
        if (grid_link is not None
                and grid_link not in self.applied_to
                and (filter is None or filter(grid_link.obj))):

            # find the new central link if asked.
            if set_center is not None and set_center(grid_link.obj):
                self.new_center = grid_link

            # remember where we've been so we don't repeat ourselves.
            self.applied_to.add(grid_link)

            # Apply function to this link and then proceed to all other
            # connected links.
            func(grid_link.obj)
            self._apply(func, filter, set_center, grid_link.left)
            self._apply(func, filter, set_center, grid_link.right)
            self._apply(func, filter, set_center, grid_link.up)
            self._apply(func, filter, set_center, grid_link.down)


class GridLink(object):
    """Class representing a link in the Grid contain links to all adjacent links.
    """
    def __init__(self, obj):
        self.obj = obj
        self.left = None
        self.right = None
        self.up = None
        self.down = None

    def __repr__(self):
        return self.__str__()

    def __str__(self):
        return "{obj:%s : left:%s right:%s up:%s down:%s}" % (
            self.obj,
            self.left.obj if self.left else None,
            self.right.obj if self.right else None,
            self.up.obj if self.up else None,
            self.down.obj if self.down else None)

    
if __name__ == "__main__":

    grid_str = """\
1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
"""

    objs = {}
    for y, line in enumerate(grid_str.split('\n')):
        for x, obj in enumerate(line.split()):
            objs[(x, y)] = obj

    grid = Grid(objs, (2, 2))

    res = []
    func = lambda x : res.append(int(x))
    filter = lambda x: int(x) > 3 and int(x) < 18
    
    grid.apply(func, filter)
    res_str = ' '.join([str(i) for i in sorted(res)])
    print res_str
    assert res_str == "4 5 6 7 8 9 10 11 12 13 14 15 16 17"